package leetcode_题库;

import java.util.HashSet;
import java.util.Set;

/**
 * Created by IntelliJ IDEA.
 *
 * @ProjectName leetcode
 * @Author Ding
 * @CreateTime 2022/8/29 9:32 星期一
 */
public class _112_路径总和 {

    /**
     * > 2022/08/29 09:43:54
     * 解答成功:
     * 	执行耗时:1 ms,击败了15.68% 的Java用户
     * 	内存消耗:41.9 MB,击败了5.07% 的Java用户
     */
    Set<Integer> set;

    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) {
            //为空，直接false，不可能有任何targetSum
            return false;
        }
        //初始化哈希表
        set = new HashSet<>();
        //深优递归
        dfs(root, 0);
        //是否存在
        return set.contains(targetSum);
    }

    public void dfs(TreeNode n, int sum) {
        //左右孩子都是null，是叶子结点，set add
        if (n.left == null && n.right == null) {
            set.add(n.val + sum);
        }
        //左孩子不是空，递归左孩子
        if (n.left != null) {
            dfs(n.left, n.val + sum);
        }
        //右孩子不是空，递归右孩子
        if (n.right != null) {
            dfs(n.right, n.val + sum);
        }
    }

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}
